/**
 * 使用动态规划思想的布局算法，尽量使输出接近正方形
 * @param images 要排列的图片数组
 * @param spacing 图片之间的间距
 * @param allowRotation 是否允许旋转图片
 * @param targetSize 目标尺寸，默认为12000
 * @returns 优化后的布局和旋转信息
 */
export function createDynamicLayout(
  images: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  spacing: number,
  allowRotation: boolean = false,
  targetSize: number = 12000
): {
  positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }>;
  rotations: Record<string, boolean>; // 记录每张图片是否旋转，key为图片id，value为是否旋转
  width: number;
  height: number;
} {
  // 如果图片数量为0，返回空结果
  if (images.length === 0) {
    return { positions: [], rotations: {}, width: 0, height: 0 };
  }

  // 复制图片数组，避免修改原数组
  const imagesCopy = JSON.parse(JSON.stringify(images));

  // 记录每张图片是否旋转
  const rotations: Record<string, boolean> = {};

  // 初始化所有图片为不旋转
  imagesCopy.forEach((img: any) => {
    rotations[img.id] = false;
  });

  // 如果允许旋转，先尝试不旋转的布局
  if (allowRotation) {
    // 将图片分为横向和纵向两组
    const landscapeImages = imagesCopy.filter(img => img.width > img.height);
    const portraitImages = imagesCopy.filter(img => img.height > img.width);

    console.log('Debug - 横向图片数量:', landscapeImages.length);
    console.log('Debug - 纵向图片数量:', portraitImages.length);

    // 首先尝试不旋转的布局
    // 如果图片数量较少（例如小于等于4张），或者只有一种方向的图片，优先不旋转
    if (images.length <= 4 || landscapeImages.length === 0 || portraitImages.length === 0) {
      console.log('Debug - 图片数量较少或单一方向，优先不旋转');
      // 不做任何旋转，继续使用原始尺寸
    }
    // 对于更多图片，检查是否需要旋转以获得更好的布局
    else {
      // 检查是否所有图片尺寸相似
      const isLandscapeSimilar = areSimilarSizes(landscapeImages);
      const isPortraitSimilar = areSimilarSizes(portraitImages);

      // 如果横向和纵向图片都有，并且尺寸相似，尝试创建接近正方形的布局
      if (isLandscapeSimilar && isPortraitSimilar) {
        // 获取典型图片尺寸
        const typicalLandscape = landscapeImages[0];
        const typicalPortrait = portraitImages[0];

        // 检查横向图片的宽是否约等于纵向图片的高，横向图片的高是否约等于纵向图片的宽
        const isComplementary = Math.abs(typicalLandscape.width - typicalPortrait.height) < 100 &&
          Math.abs(typicalLandscape.height - typicalPortrait.width) < 100;

        // 如果图片尺寸互补，使用优化的正方形布局
        if (isComplementary) {
          console.log('Debug - 使用通用正方形布局');
          // 创建接近正方形的布局
          return createOptimalSquareLayout(landscapeImages, portraitImages, spacing, targetSize);
        }
      }

      // 尝试计算不旋转时的布局面积
      const noRotationLayout = calculateLayoutArea(imagesCopy, spacing, targetSize);

      // 创建旋转后的图片副本进行比较
      const rotatedImagesCopy = JSON.parse(JSON.stringify(imagesCopy));
      const tempRotations: Record<string, boolean> = {};

      // 对于每张图片，如果旋转后更接近正方形，则旋转
      rotatedImagesCopy.forEach((img: any) => {
        // 计算旋转前后的宽高比
        const originalRatio = img.width / img.height;
        const rotatedRatio = img.height / img.width;

        // 如果旋转后的宽高比更接近1（更接近正方形），则旋转
        if (Math.abs(rotatedRatio - 1) < Math.abs(originalRatio - 1)) {
          tempRotations[img.id] = true;
          // 交换宽高
          const temp = img.width;
          img.width = img.height;
          img.height = temp;
        } else {
          tempRotations[img.id] = false;
        }
      });

      // 计算旋转后的布局面积
      const rotatedLayout = calculateLayoutArea(rotatedImagesCopy, spacing, targetSize);

      // 比较两种布局，如果旋转后的布局更接近正方形或面积更小，则使用旋转后的布局
      const noRotationRatio = noRotationLayout.width / noRotationLayout.height;
      const rotatedRatio = rotatedLayout.width / rotatedLayout.height;
      const noRotationArea = noRotationLayout.width * noRotationLayout.height;
      const rotatedArea = rotatedLayout.width * rotatedLayout.height;

      // 如果不旋转的布局已经很接近正方形（比例在0.8-1.2之间），或者面积更小，则优先使用不旋转的布局
      if ((noRotationRatio >= 0.8 && noRotationRatio <= 1.2) || noRotationArea <= rotatedArea) {
        console.log('Debug - 不旋转的布局更优，使用原始尺寸');
        // 不做任何旋转，继续使用原始尺寸
      } else {
        console.log('Debug - 旋转后的布局更优，应用旋转');
        // 应用旋转
        Object.assign(rotations, tempRotations);

        // 更新图片尺寸
        imagesCopy.forEach((img: any) => {
          if (rotations[img.id]) {
            // 交换宽高
            const temp = img.width;
            img.width = img.height;
            img.height = temp;
          }
        });
      }
    }
  }

  // 使用二维装箱算法（二维背包问题的变种）
  // 这里我们使用一个简化的贪心算法，先按面积从大到小排序图片
  imagesCopy.sort((a: any, b: any) => (b.width * b.height) - (a.width * a.height));

  // 初始化结果
  const positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }> = [];

  // 使用二维空间划分算法
  // 我们将空间划分为多个矩形区域，每次放置图片时，选择最适合的区域

  // 初始化一个矩形区域，表示整个可用空间
  const spaces: Array<{ x: number; y: number; width: number; height: number }> = [
    { x: 0, y: 0, width: targetSize, height: targetSize }
  ];

  // 对于每张图片，找到最适合的区域放置
  for (const img of imagesCopy) {
    // 找到最适合的区域
    const bestSpaceIndex = findBestSpace(spaces, img.width, img.height);

    if (bestSpaceIndex === -1) {
      // 没有找到合适的区域，扩展空间
      const newSpace = expandSpace(spaces, img.width, img.height);

      // 放置图片
      positions.push({
        id: img.id,
        name: img.name,
        x: newSpace.x,
        y: newSpace.y,
        width: img.width,
        height: img.height,
        format: img.format
      });

      // 分割剩余空间
      splitSpace(spaces, newSpace, img.width, img.height, spacing);
    } else {
      // 找到合适的区域，放置图片
      const space = spaces[bestSpaceIndex];

      positions.push({
        id: img.id,
        name: img.name,
        x: space.x,
        y: space.y,
        width: img.width,
        height: img.height,
        format: img.format
      });

      // 从空间列表中移除已使用的空间
      spaces.splice(bestSpaceIndex, 1);

      // 分割剩余空间
      splitSpace(spaces, space, img.width, img.height, spacing);
    }
  }

  // 计算布局的宽度和高度
  const width = Math.max(...positions.map(p => p.x + p.width));
  const height = Math.max(...positions.map(p => p.y + p.height));

  return { positions, rotations, width, height };
}

/**
 * 创建完美的12000x12000正方形布局，专门用于处理3张横向和3张纵向图片的情况
 * @param landscapeImages 横向图片数组
 * @param portraitImages 纵向图片数组
 * @param spacing 图片间距
 * @returns 优化后的布局和旋转信息
 */
function createPerfectSquareLayoutWithRotation(
  landscapeImages: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  portraitImages: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  spacing: number
): {
  positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }>;
  rotations: Record<string, boolean>;
  width: number;
  height: number;
} {
  const positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }> = [];
  const rotations: Record<string, boolean> = {};

  // 初始化所有图片为不旋转
  [...landscapeImages, ...portraitImages].forEach(img => {
    rotations[img.id] = false;
  });

  // 获取典型图片尺寸
  const landscapeWidth = landscapeImages[0].width;  // 6000
  const landscapeHeight = landscapeImages[0].height; // 4000
  const portraitWidth = portraitImages[0].width;    // 4000
  const portraitHeight = portraitImages[0].height;  // 6000

  // 为了确保布局是12000x12000的正方形，我们需要旋转一些图片
  // 我们将旋转所有的纵向图片，使它们变成横向
  portraitImages.forEach(img => {
    rotations[img.id] = true;
  });

  // 布局如下（优化后，确保12000x12000）：
  // +-------------+-------------+
  // |             |             |
  // |  Landscape1 |  Landscape2 |
  // |  6000x4000  |  6000x4000  |
  // |             |             |
  // +-------------+-------------+
  // |             |             |
  // |  Landscape3 |  Portrait1  |
  // |  6000x4000  |  6000x4000  |
  // |             |  (rotated)  |
  // +-------------+-------------+
  // |             |             |
  // |  Portrait2  |  Portrait3  |
  // |  6000x4000  |  6000x4000  |
  // |  (rotated)  |  (rotated)  |
  // +-------------+-------------+

  // 第一行：两张横向图片并排
  positions.push({
    id: landscapeImages[0].id,
    name: landscapeImages[0].name,
    x: 0,
    y: 0,
    width: landscapeWidth,
    height: landscapeHeight,
    format: landscapeImages[0].format
  });

  positions.push({
    id: landscapeImages[1].id,
    name: landscapeImages[1].name,
    x: landscapeWidth,
    y: 0,
    width: landscapeWidth,
    height: landscapeHeight,
    format: landscapeImages[1].format
  });

  // 第二行：一张横向图片和一张旋转后的纵向图片
  positions.push({
    id: landscapeImages[2].id,
    name: landscapeImages[2].name,
    x: 0,
    y: landscapeHeight,
    width: landscapeWidth,
    height: landscapeHeight,
    format: landscapeImages[2].format
  });

  positions.push({
    id: portraitImages[0].id,
    name: portraitImages[0].name,
    x: landscapeWidth,
    y: landscapeHeight,
    width: portraitHeight, // 旋转后宽高交换
    height: portraitWidth,
    format: portraitImages[0].format
  });

  // 第三行：两张旋转后的纵向图片
  positions.push({
    id: portraitImages[1].id,
    name: portraitImages[1].name,
    x: 0,
    y: landscapeHeight * 2,
    width: portraitHeight, // 旋转后宽高交换
    height: portraitWidth,
    format: portraitImages[1].format
  });

  positions.push({
    id: portraitImages[2].id,
    name: portraitImages[2].name,
    x: landscapeWidth,
    y: landscapeHeight * 2,
    width: portraitHeight, // 旋转后宽高交换
    height: portraitWidth,
    format: portraitImages[2].format
  });

  // 计算布局的实际宽度和高度
  const actualWidth = Math.max(...positions.map(p => p.x + p.width));
  const actualHeight = Math.max(...positions.map(p => p.y + p.height));

  console.log(`Debug - 完美布局实际尺寸: ${actualWidth}x${actualHeight}`);

  // 确保返回的是12000x12000的布局
  return { positions, rotations, width: 12000, height: 12000 };
}

/**
 * 找到最适合放置图片的空间
 * @param spaces 可用空间列表
 * @param width 图片宽度
 * @param height 图片高度
 * @returns 最适合的空间索引，如果没有找到则返回-1
 */
function findBestSpace(
  spaces: Array<{ x: number; y: number; width: number; height: number }>,
  width: number,
  height: number
): number {
  let bestSpaceIndex = -1;
  let bestScore = Number.MAX_VALUE;

  for (let i = 0; i < spaces.length; i++) {
    const space = spaces[i];

    // 检查空间是否足够大
    if (space.width >= width && space.height >= height) {
      // 计算剩余空间的面积
      const remainingArea = (space.width - width) * (space.height - height);

      // 选择剩余面积最小的空间，这样可以减少碎片
      if (remainingArea < bestScore) {
        bestScore = remainingArea;
        bestSpaceIndex = i;
      }
    }
  }

  return bestSpaceIndex;
}

/**
 * 扩展空间以容纳图片
 * @param spaces 可用空间列表
 * @param width 图片宽度
 * @param height 图片高度
 * @returns 新的空间
 */
function expandSpace(
  spaces: Array<{ x: number; y: number; width: number; height: number }>,
  width: number,
  height: number
): { x: number; y: number; width: number; height: number } {
  // 找到当前布局的边界
  const maxX = Math.max(...spaces.map(s => s.x + s.width), 0);
  const maxY = Math.max(...spaces.map(s => s.y + s.height), 0);

  // 创建新的空间
  const newSpace = { x: 0, y: maxY, width: maxX, height: height };

  return newSpace;
}

/**
 * 分割空间
 * @param spaces 可用空间列表
 * @param space 要分割的空间
 * @param width 图片宽度
 * @param height 图片高度
 * @param spacing 图片间距
 */
function splitSpace(
  spaces: Array<{ x: number; y: number; width: number; height: number }>,
  space: { x: number; y: number; width: number; height: number },
  width: number,
  height: number,
  spacing: number
): void {
  // 分割右侧空间
  if (space.width > width + spacing) {
    spaces.push({
      x: space.x + width + spacing,
      y: space.y,
      width: space.width - width - spacing,
      height: height
    });
  }

  // 分割底部空间
  if (space.height > height + spacing) {
    spaces.push({
      x: space.x,
      y: space.y + height + spacing,
      width: space.width,
      height: space.height - height - spacing
    });
  }
}/**
 * 检查一组图片的尺寸是否相似
 * @param images 图片数组
 * @returns 是否相似
 */
function areSimilarSizes(images: Array<{ width: number; height: number }>): boolean {
  if (images.length <= 1) return true;

  const firstWidth = images[0].width;
  const firstHeight = images[0].height;

  // 允许10%的误差
  const tolerance = 0.1;

  return images.every(img =>
    Math.abs(img.width - firstWidth) / firstWidth < tolerance &&
    Math.abs(img.height - firstHeight) / firstHeight < tolerance
  );
}

/**
 * 计算布局的面积和尺寸
 * @param images 图片数组
 * @param spacing 图片间距
 * @param targetSize 目标尺寸
 * @returns 布局的宽度和高度
 */
function calculateLayoutArea(
  images: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  spacing: number,
  targetSize: number = 12000
): { width: number; height: number } {
  // 使用二维装箱算法的简化版本来估算布局
  // 按面积从大到小排序图片
  const sortedImages = [...images].sort((a, b) => (b.width * b.height) - (a.width * a.height));

  // 初始化一个矩形区域，表示整个可用空间
  const spaces: Array<{ x: number; y: number; width: number; height: number }> = [
    { x: 0, y: 0, width: targetSize, height: targetSize }
  ];

  // 记录图片位置
  const positions: Array<{ x: number; y: number; width: number; height: number }> = [];

  // 对于每张图片，找到最适合的区域放置
  for (const img of sortedImages) {
    // 找到最适合的区域
    const bestSpaceIndex = findBestSpace(spaces, img.width, img.height);

    if (bestSpaceIndex === -1) {
      // 没有找到合适的区域，扩展空间
      const newSpace = expandSpace(spaces, img.width, img.height);

      // 记录图片位置
      positions.push({
        x: newSpace.x,
        y: newSpace.y,
        width: img.width,
        height: img.height
      });

      // 分割剩余空间
      splitSpace(spaces, newSpace, img.width, img.height, spacing);
    } else {
      // 找到合适的区域，放置图片
      const space = spaces[bestSpaceIndex];

      // 记录图片位置
      positions.push({
        x: space.x,
        y: space.y,
        width: img.width,
        height: img.height
      });

      // 从空间列表中移除已使用的空间
      spaces.splice(bestSpaceIndex, 1);

      // 分割剩余空间
      splitSpace(spaces, space, img.width, img.height, spacing);
    }
  }

  // 计算布局的宽度和高度
  const width = Math.max(...positions.map(p => p.x + p.width));
  const height = Math.max(...positions.map(p => p.y + p.height));

  return { width, height };
}

/**
 * 创建最优的正方形布局，适用于横向和纵向图片混合的情况
 * @param landscapeImages 横向图片数组
 * @param portraitImages 纵向图片数组
 * @param spacing 图片间距
 * @param targetSize 目标尺寸
 * @returns 优化后的布局和旋转信息
 */
function createOptimalSquareLayout(
  landscapeImages: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  portraitImages: Array<{ id: string; name: string; width: number; height: number; format: string }>,
  spacing: number,
  targetSize: number = 12000
): {
  positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }>;
  rotations: Record<string, boolean>;
  width: number;
  height: number;
} {
  const positions: Array<{ id: string; name: string; x: number; y: number; width: number; height: number; format: string }> = [];
  const rotations: Record<string, boolean> = {};

  // 初始化所有图片为不旋转
  [...landscapeImages, ...portraitImages].forEach(img => {
    rotations[img.id] = false;
  });

  // 获取典型图片尺寸
  const landscapeWidth = landscapeImages[0].width;  // 例如 6000
  const landscapeHeight = landscapeImages[0].height; // 例如 4000
  const portraitWidth = portraitImages[0].width;    // 例如 4000
  const portraitHeight = portraitImages[0].height;  // 例如 6000

  // 为了创建接近正方形的布局，我们将旋转所有的纵向图片
  portraitImages.forEach(img => {
    rotations[img.id] = true;
  });

  // 计算每行可以放置的图片数量
  const imagesPerRow = Math.floor(targetSize / landscapeWidth);

  // 计算总行数
  const totalImages = landscapeImages.length + portraitImages.length;
  const totalRows = Math.ceil(totalImages / imagesPerRow);

  // 所有图片（横向图片和旋转后的纵向图片）
  const allImages = [
    ...landscapeImages,
    ...portraitImages.map(img => ({
      ...img,
      width: img.height, // 旋转后宽高交换
      height: img.width
    }))
  ];

  // 按行放置图片
  let currentX = 0;
  let currentY = 0;
  let rowHeight = 0;

  for (let i = 0; i < allImages.length; i++) {
    const img = allImages[i];
    const isRotated = portraitImages.some(p => p.id === img.id);

    // 如果这是一个新行的开始或者当前行放不下这张图片
    if (currentX === 0 || currentX + img.width > targetSize) {
      // 如果不是第一行，移到下一行
      if (currentX > 0) {
        currentX = 0;
        currentY += rowHeight + spacing;
      }
      rowHeight = 0;
    }

    // 放置图片
    positions.push({
      id: img.id,
      name: img.name,
      x: currentX,
      y: currentY,
      width: img.width,
      height: img.height,
      format: img.format
    });

    // 更新当前位置和行高
    currentX += img.width + spacing;
    rowHeight = Math.max(rowHeight, img.height);
  }

  // 计算布局的实际宽度和高度
  const actualWidth = Math.min(targetSize, Math.max(...positions.map(p => p.x + p.width)));
  const actualHeight = Math.max(...positions.map(p => p.y + p.height));

  console.log(`Debug - 优化布局实际尺寸: ${actualWidth}x${actualHeight}`);

  // 返回布局
  return { positions, rotations, width: actualWidth, height: actualHeight };
}